package 算法;


import java.util.*;

/**
 * @author zhangmin
 * @create 2021-12-18 13:45
 *
 * 其他算法
 */
public class Other07 {

    /**==============================================================================================================================================
     * JZ66 构建乘积数组
     * 给定一个数组 A[0,1,...,n-1] ,请构建一个数组 B[0,1,...,n-1] ,其中 B 的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]（除 A[i] 以外的全部元素的的乘积）。
     * 程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]），对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。
     * 思路：构建前缀乘积与后缀乘积
     * */
    public int[] multiply(int[] A) {
        int n=A.length;
        if (n==1) return new int[0];
        int[] pre=new int[n];
        pre[0]=A[0];
        int[] post=new int[n];
        post[n-1]=A[n-1];
        for (int i = 1; i < n; i++) {
            pre[i]=pre[i-1]*A[i];
            post[n-i-1]=post[n-i]*A[n-i-1];
        }
        int[] B=new int[n];
        B[0]=post[1];
        B[n-1]=pre[n-2];
        for (int i = 1; i < n-1; i++) {
            B[i]=pre[i-1]*post[i+1];
        }
        return B;
    }

    /**==============================================================================================================================================
     * JZ50 第一个只出现一次的字符
     * 在一个长为 n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
     * 优先队列,set记录是否重复，遍历字符串
     * */
    public int FirstNotRepeatingChar(String str) {
        int n=str.length();
        Queue<Character> queue=new LinkedList<>();
        Set<Character> set=new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (set.add(str.charAt(i))){
                queue.add(str.charAt(i));
            }else {
                queue.remove(str.charAt(i));
            }
        }
        return queue.isEmpty()?-1:str.indexOf(queue.peek());
    }

    /**==============================================================================================================================================
     * JZ5 替换空格
     * 请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
     * */
    public String replaceSpace1 (String s) {
        return s.replace(" ","%20");
    }
    public String replaceSpace (String s) {
        String res="";
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)==' '){
                res+="%20";
            }else {
                res+=s.charAt(i);
            }
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ21 调整数组顺序使奇数位于偶数前面(一)
     * 输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，
     * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
     * 两个数组分别记录奇数和偶数
     * */
    public int[] reOrderArray (int[] array) {
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i]%2==1){
                list1.add(array[i]);
            }else {
                list2.add(array[i]);
            }
        }
        int[] res=new int[array.length];
        int index=0;
        for (int i = 0; i < list1.size(); i++) {
            res[index++]=list1.get(i);
        }
        for (int i = 0; i < list2.size() ;i++) {
            res[index++]=list2.get(i);
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ39 数组中出现次数超过一半的数字
     * 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 排序后返回中间位置，即为答案
     * */
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        return array[array.length/2];
    }
    /**==============================================================================================================================================
     * JZ43 整数中1出现的次数（从1到n整数中1出现的次数）
     * 输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
     * 思路：遍历n的每一位为cur，cur前的为高位high，后面的为低位low，digit=10^i表示位因子，记录cur是哪一位
     * 当 cur = 0时： 此位 1 的出现次数只由高位 high 决定，计算公式为：high×digit
     * 当cur=1时：此位1的处出现次数由高位和低位同时决定：high*digit+low+1
     * 当cur=2.3...9时：此位1的出现次数只由高位决定：(high+1)*dight
     * */
    public int NumberOf1Between1AndN_Solution(int n) {
        int digit=1,res=0;
        //cur开始为最后一位
        int high=n/10,low=0,cur=n%10;
        while (high!=0||cur!=0){
            if (cur==0) res+=high*digit;
            else if (cur==1) res+=high*digit+low+1;
            else res+=(high+1)*digit;
            low+=cur*digit;
            cur=high%10;
            high=high/10;
            digit=digit*10;
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ45 把数组排成最小的数
     * 输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
     * 重写比较函数，变为比较两者的不同拼接顺序的结果比较
     * 先将int数组转换为String数组，自定义比较规则
     * 若拼接字符串 x + y > y + x，则 x “大于” y ；y应该在x的左边,反之，若 x + y < y + x ，则 x “小于” y ；表示x应该在y的左边
     * */
    public String PrintMinNumber(int [] numbers) {
        String[] ns=new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            ns[i]=String.valueOf(numbers[i]);
        }
        Arrays.sort(ns, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1+o2).compareTo(o2+o1);
            }
        });
        String res="";
        for (String s:ns) {
            res+=s;
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ49 丑数
     * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
     * 最小堆
     * */
    public int GetUglyNumber_Solution(int index) {
        if (index==1) return 1;
        Queue<Long> queue=new PriorityQueue<>();
        queue.add(1L);
        int[] primes={2,3,5};
        Set<Long> set=new HashSet<>();
        set.add(1L);
        int res=0;
        for (int i = 0; i < index ; i++) {
            Long cur=queue.poll();
            res= Math.toIntExact(cur);
            for (int p:primes) {
                if (set.add(p*cur)){
                    queue.offer(p*cur);
                }
            }
        }
        return res;
    }
    /**==============================================================================================================================================
     * JZ74 和为S的连续正数序列
     * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
     * 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
     * 双指针，滑动窗口:窗口内和小于s时右指针扩大窗口，大于s时，左指针缩小窗口
     * */
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        if (sum==0) return new ArrayList<>();
        ArrayList<ArrayList<Integer>> res=new ArrayList();
        int i=1,j=2;
        while (i<j){
            int wsum=(i+j)*(j-i+1)/2;
            if (wsum==sum){
                ArrayList<Integer> list=new ArrayList<>();
                for (int k = i; k <=j ; k++) {
                    list.add(k);
                }
                res.add(list);
                //扩大窗口
                j++;
            }else if (wsum<sum){
                //扩大窗口
                j++;
            }else {
                //缩小窗口
                i++;
            }
        }
        return res;
    }
    /**==============================================================================================================================================
     * JZ57 和为S的两个数字
     * 输入一个递增排序的数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
     * 双指针
     * */
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int left=0,right=array.length-1;
        while (left<right){
            int s=array[left]+array[right];
            if (s==sum){
                ArrayList<Integer> res=new ArrayList<>();
                res.add(array[left]);
                res.add(array[right]);
                return res;
            }else if (s<sum){
                left++;
            }else if (s>sum){
                right--;
            }
        }
        return new ArrayList<>();
    }

    /**==============================================================================================================================================
     * JZ58 左旋转字符串
     * 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列  S ，
     * 请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc” 。是不是很简单？OK，搞定它！
     * */
    public String LeftRotateString(String str,int n) {
        if (str.length()==0) return "";
        n=n%str.length();
        return str.substring(n)+str.substring(0,n);
    }

    /**==============================================================================================================================================
     * JZ62 孩子们的游戏(圆圈中最后剩下的数)
     * 首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，
     * 然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，
     * 可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？
     * 模拟迭代，f[1] = 0,f[2] = (f{1] + m) % 2,f[3] = (f[2] + m) % 3...f[n] = (f[n-1] + m) % n
     * */
    public int LastRemaining_Solution(int n, int m) {
        if (n<=0) return -1;
        int index=0;
        for (int i = 2; i <=n ; i++) {
            index=(index+m)%i;
        }
        return index;
    }

    /**==============================================================================================================================================
     * JZ75 字符流中第一个不重复的字符
     * 请实现一个函数用来找出字符流中第一个只出现一次的字符。
     * 用队列记录出现的顺序，用set判断是否重复
     * */
    Queue<Character> queue=new LinkedList<>();
    Set<Character> set=new HashSet<>();
    public void Insert(char ch)
    {
        if (set.add(ch)){
            queue.offer(ch);
        }else {
            queue.remove(ch);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        return queue.isEmpty()?'#':queue.peek();
    }

    /**==============================================================================================================================================
     * JZ14 剪绳子
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），
     * 每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？
     * 思路：1、当剪开的每一段等长时成绩最大  2、剪开每段为3时乘积最大
     * target%3=a...b
     * b==0,返回3^a
     * b==1,返回3^(a-1)*4;
     * b==2,返回3^a*2
     * */
    public int cutRope(int target) {
        int a=target/3,b=target%3;
        if (b==0) return (int) Math.pow(3,a);
        else if (b==1) return (int) (Math.pow(3,a-1)*4);
        else return (int) (Math.pow(3,a)*2);
    }


    /**==============================================================================================================================================
     * JZ83 剪绳子（进阶版）
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），
     * 每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？由于答案过大，请对 998244353 取模。
     * 快速乘，并且每次%mod,避免溢出
     * */
    public long cutRope (long number) {
        if (number<=3) return number-1;
        long mod=998244353;
        long res=1,x=3,a=(number/3)-1;
        while (a>0){
            //当a为奇数时，只需要乘1个x
            if (a%2==1) res=(res*x)%mod;
            x=(x*x)%mod;
            a=a/2;
        }
        long b=number%3;
        if (b==0) return (res*3)%mod;
        else if (b==1) return (res*4)%mod;
        else return (res*6)%mod;
    }

    /**==============================================================================================================================================
     * JZ81 调整数组顺序使奇数位于偶数前面(二)
     * 输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，
     * 所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。时间复杂度 O(n)，空间复杂度 O(1)
     * 双指针
     * */
    public int[] reOrderArrayTwo (int[] array) {
        int left=0,right=array.length-1;
        while (left<right){
            while (array[left]%2==1) left++;
            while (array[right]%2==0) right--;
            if (left<right){
                int t=array[left];
                array[left]=array[right];
                array[right]=t;
            }
        }
        return array;
    }

    /**==============================================================================================================================================
     * JZ17 打印从1到最大的n位数
     * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
     * 计算n位数的最大值
     * */
    public int[] printNumbers (int n) {
        int max=9;
        for (int i = 1; i < n; i++) {
            max=max*10+9;
        }
        int[] res=new int[max];
        for (int i = 0; i < max; i++) {
            res[i]=i+1;
        }
        return res;
    }



}
